package com.msb.class03;

import com.msb.class02.Random;
import org.w3c.dom.ls.LSOutput;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Auther: jiudianliu
 * @Date: 2024/2/6 - 02 - 06 - 21:45
 * @Description: com.msb.class03
 * @version: 1.0
 */
public class MostLeftRightNum {


    // 在一个随机有序数组中，找到>=num 最左位置

    public static void main(String[] args) {
        int arrMaxValues = 5 ;
        int arrMaxLen = 10 ;
        int num = (int) (Math.random() * (arrMaxValues + 1));
        int testTimes = 100000 ;
        System.out.println("测试开始");
        for (int i =0 ; i <= testTimes ; i++) {
            int[] arr = orderArray(arrMaxValues , arrMaxLen);
            if (mostLeftOneNum(arr , num) != check(arr , num)){
                arrPrint(arr);
                break;
            }
        }
        System.out.println("测试结束");
    }


    // 创建有序随机数组
    public static int[] orderArray(int arrMaxValues , int arrMaxLen){
        int[] arr = new int[(int) ((arrMaxLen + 1) * Math.random())];
        for ( int i = 0 ; i < arr.length ; i++ ) {
            arr[i] = (int) ((arrMaxValues + 1) * Math.random()) - (int) ((arrMaxValues * Math.random()));
        }
        // 利用Arrays 的 sort 方法  对数组进行排序
        Arrays.sort(arr);
        return arr ;
    }

    // 打印有序数组
    public static void arrPrint(int[] arr){
        for (int num : arr){
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 测试方法
    public static int check(int[] arr , int num){
        int ans = -1 ;
        for (int i = 0 ; i < arr.length ; i++){
            if (arr[i] >= num){
                return i ;
            }
        }
        return ans ;
    }

    // 在一个随机有序数组中，找到>=num 最左位置
    public static int mostLeftOneNum(int[] arr , int num){
        if (arr == null || arr.length == 0){
            return -1 ;
        }
        int L = 0 ;
        int R = arr.length - 1 ;
        int ans = -1 ;
        while(L <= R){
            int mid = ( L + R ) / 2 ;
            if (arr[mid] >= num){
                ans = mid ;
                R = mid - 1 ;
            } else {
                L = mid + 1 ;
            }
        }
        return ans ;
    }
}
